Ewaluacja

Limit pamięci: 128 MB

Dane jest wyrażenie matematyczne , w którym występują: stałe od 0 do 9, zmienne od do , a także operacje: dodawania, mnożenia i potęgowania o stałym wykładniku. Co ciekawe, każda ze zmiennych występuje w wyrażeniu co najwyżej raz. Zastanawiamy się, dla danej liczby pierwszej , ile pierwiastków modulo ma wielomian wyznaczony przez to wyrażenie. Innymi słowy, pytamy, ile jest podstawień liczb od do pod zmienne występujące w , dla których wartość wyrażenia jest podzielna przez . Ponieważ szukana liczba pierwiastków może być duża, wystarczy nam reszta z jej dzielenia przez .

Przykładowo, wielomian reprezentowany przez wyrażenie

ma 15 pierwiastków modulo , m.in. następujące trzy pierwiastki:

Formalnie, wyrażenie definiujemy następująco:

• Każda stała 0, 1, ..., 9 jest wyrażeniem.
• Każda zmienna a, b, ..., z jest wyrażeniem.
• Jeśli A i B są dowolnymi wyrażeniami, to wyrażeniami są także (A+B) i (A*B). Pierwsze z nich oznacza sumę wyrażeń A i B, zaś drugie - ich iloczyn.
• Jeśli A jest dowolnym wyrażeniem, a B jest stałą z zakresu 2, 3, ..., 9, to wyrażeniem jest także (A^B) (wyrażenie A do potęgi B).

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę pierwszą (). Drugi wiersz zawiera wyrażenie zgodne z podaną specyfikacją, opisane przez ciąg złożony z co najwyżej 300 znaków 0, 1, ..., 9, a, b, ..., z, +, *, ^, (, ). W podanym ciągu nie występują odstępy.

Wyjście

Oznaczmy przez liczbę pierwiastków modulo wielomianu . Twój program powinien wypisać jedną nieujemną liczbę całkowitą: resztę z dzielenia przez .

Przykład

Dla danych wejściowych:

3
(((a+y)*(z+8))^2)

poprawną odpowiedzią jest:

15

Autor zadania: Jakub Radoszewski.